The present invention relates to computer software utility programs, and more specifically to programs in the field of computer aided design (CAD), computer aided manufacturing (CAM), and computer aided engineering (CAE), and in particular the use of such systems for determining the proper physical location of robots in a manufacturing facility.
Robots are used extensively in automated manufacturing processes. Robots can be employed to perform repetitive tasks in a precise and time efficient manner. For example, robots are employed in automobile production lines to apply spot welds to automobile frames, resulting in more precise placement of welds, in a more time efficient manner, than can be accomplished through the use of manual labor. In a typical manufacturing process, a robot performs a repetitive sequence of point-to-point movements, coming to a stop at each point. For example, the robot will apply a spot weld to an assembly at each programmed stop location. As used herein, the term xe2x80x9cwork pointxe2x80x9d means each stop location at which work is to be performed by the robot on a workpiece. The term xe2x80x9cworkplanxe2x80x9d refers to a set of work points, and xe2x80x9ctrajectoryxe2x80x9d refers to the path taken by the robot end-effector when moving directly from one work point to the next in the workplan.
The productivity of a robot can be improved considerably by minimizing the cycle time for completing a workplan. For a given robot, cycle time depends on many parameters, such as the position of the manipulator relative to the task, the sequence in which the points are visited, the maximum velocities and accelerations of the actuators, the relative position of the points, and the configuration of the robotic arm. A robot ill-placed at its workstation risks inefficient operation and even failure. Thus, there is a need for a system for choosing robot position so that cycle time can be minimized for a specified workplan.
Existing CAD systems can be used to model a manufacturing facility including robots. Such CAD systems, when equipped with data detailing the configuration of the items upon which work will be performed, the configuration of objects in the workplace environment, and the configuration of the robots themselves, are used to model the workplace. Each item can be placed within the workplace graphically for the purpose of modeling the facility. Robots can then be moved graphically to check for task feasibility and efficiency. In known CAD systems, calculating the cycle time for a given workplan involves a time consuming trail and error loop, which is to be carried out by the user, in which the robotic movement is simulated graphically. To reduce cycle time, the operator must choose a set of proposed robot base positions, and then run a simulation of the robot movement for each proposed robot base position to obtain a comparison of position feasibility and cycle time. This involves extensive CPU time and is inefficient.
There is therefore a need for an easy-to-use system for optimizing robot position to achieve a low cycle time, which does not involve a time-consuming iterative process which must be performed by the user.
Accordingly, the present invention provides a system, method and apparatus for finding the optimal possible placement of the base of a robot with respect to a workpiece in an efficient manner. Optimal placement is defined as the placement which will allow the robot manipulator tool to be moved through its trajectory for a given workplan in a minimum amount of time. To find the optimum location, an area containing a number of possible locations for robot base placement is searched using an optimization algorithm. According to an aspect of the invention, the area to be searched containing the possible robot base locations is minimized so that the number of possible base locations to test, or xe2x80x9csearchxe2x80x9d, for optimization is reduced. A first step in minimizing the search space consists of calculating an xe2x80x9cacceptable robot base location domainxe2x80x9d. This domain defines an area within a horizontal plane in which the robot base must be placed so that the manipulator tool of the robot will be able to reach each of the intended work points in the workplan to be performed by the robot. The factors determining this domain are the location of all the work points, and the geometry and kinematic profile of the robot.
Following the identification of the acceptable robot base location domain, according to an aspect of the invention, it is necessary to take into account the potential for collisions between the robot and its environment. To achieve this goal, a method of defining xe2x80x9cobstacle shadowsxe2x80x9d is presented, such obstacle shadows representing portions of the acceptable robot base location domain where the robot cannot be placed because doing so would result in collisions between the robot and objects in its environment when the manipulator tool is extended to a work point in the workplan. The object of the method is to find and define the xe2x80x9cobstacle shadow""sxe2x80x9d outline, by moving the robot""s base in horizontal sections of the acceptable base location domain and testing for collisions. The xe2x80x9cobstacle shadowsxe2x80x9d are subtracted from the acceptable base location domain, reducing its size, and therefore the number of possible base location positions to be searched during optimization. According to the method of the invention, after defining a global path to be followed, the robot""s base is moved step by step to achieve a goal point, normally, a work point in the workplan. When a collision is encountered, the direction of displacement is modified, and the global path for the next iteration is then redefined. This step is repeated until the goal point is reached. By moving around the obstacle shadow on the left and then on the right, a set of points from which the closed contour of the shadow can be deduced is obtained. As stated above, the closed contour of the shadow is then subtracted from the acceptable robot base location domain, resulting in a xe2x80x9cfree acceptable base location domainxe2x80x9d. When the robot base is placed anywhere within the free acceptable base location, the robot tool can reach each point where work is to be performed, i.e., each work point, without being restricted by objects in its environment. According to an aspect of the invention, the set of possible base locations may be further reduced using standard functionality available in CAD systems, such as the xe2x80x9ccollision testingxe2x80x9d function of the xe2x80x9cCATIA Design and Robot Programming Solutionxe2x80x9d system sold by Dassault-Systxc3xa8mes of Suresnes, France. Such functionality is used to determine whether collisions will occur while the robot arm is moving from work point to work point. Locations that would result in collisions are removed from consideration. According to another aspect of the invention, using standard functionality available in CAD systems, tests can be conducted to determine if re-configuration of the robot is required to move from work point to work point along the trajectory. Results that would result in reconfiguration are also removed from consideration.
Having defined a free acceptable base location domain, it is then desirable to identify specific locations within the domain for robot base placement which will achieve a minimized cycle time. According to an aspect of the invention, a modified xe2x80x9csimulated annealingxe2x80x9d method is employed to find a set of optimal positions for the robot base for minimum cycle time. The classic simulated annealing algorithm will be familiar to a person of skill in the art, and is described, for example, at S. Kirkpatrick, C. D. Gelatt, Jr. and M. P. Vecchi, xe2x80x98Optimization by Simulated Annealingxe2x80x99, Science, 220 (4598), pp. 671-680, May 1983. The conventional simulated annealing algorithm can only yield a single and isolated optimal solution to the problem, which is not satisfactory in the context of an industrial CAD system. Furthermore, simulated annealing may require long computation times, as it cannot distinguish a local minimum from an ordinary solution, unless it visits the very bottom of the local minimum. According to the invention, two features were added to the conventional simulated annealing method to build some xe2x80x9copportunismxe2x80x9d into the method.
The first feature is the use of what has been termed a xe2x80x9cfreeze-heatxe2x80x9d cycle, which corresponds to regular application of local search procedures. This feature is aimed at exploring a minimum valley as fast as possible and yields the closest local minimum in the search space. The second feature is the memorization of the local minima and their xe2x80x9cattraction areasxe2x80x9d. In this way, a minimum valley is not revisited once it has been explored, and other minima can be obtained. Such modifications yield a set of near-optimal solutions at the end of execution, together with the knowledge of their respective neighborhoods. Using this modification, there is no guarantee that the single absolute optimal location for the robot base will be found. Instead, a set of near-optimal solutions will be obtained, using substantially less computational resources than would be necessary using a classic simulated annealing method.